#include <vector>
#include <string>
#include <iostream>
#include <numeric>

using namespace std;

int kadane(const vector<int> &array){
    vector<int> result(array.size(), 0);
    
    result[0] = array[0];

    int ret = result[0];

    for(int i = 1; i < array.size(); ++i){
        result[i] = max(array[i]+result[i-1], array[i]);
        ret = max(result[i], ret);
    }
    
    return ret;
}

int main(int argc, char const *argv[])
{
    vector<int> array{3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4};
    cout << kadane(array) << endl;
    return 0;
}
